"""
插入排序
用未排序序列第一个元素，从已排序序列尾部到起始位置方向开始比较，也就是插入元素和已排序最大元素开始比较，一直找到比它小的元素位置后插入。
"""
def insertSort(array):
    n=len(array)
    for i in range(n):
        for j in range(1,i+1):
            if array[j]>array[j-1]:
                array[j], array[j - 1]=array[j-1], array[j]


if __name__ == "__main__":
    array = [3, 2, 1,8,55,43,2,1,0]
    insertSort(array)
    print(array)